#include <stdio.h>
#include <stdlib.h>

#define LH 1;
#define RH -1;
#define EH 0;

typedef int ElemType;

typedef struct BST_node
{
    ElemType data;
    int bf;
    struct BST_node *rchild, *lchild;
} *BSTree, BST_node;

BST_node *BS_search(BSTree *T, ElemType data)
{
    while (T && data != (*T)->data)
    {
        (*T) = (*T)->data > data ? (*T)->rchild : (*T)->lchild;
    }
    return *T;
}



BSTree RR_Rotate(BSTree p)
{
    // 右旋 A ↘ B ↘ C  =>  A ↙ B ↘ C
    BSTree lc = p->lchild;
    p->lchild = lc->rchild;
    lc->rchild = p;
    p = lc;
    return p;
}

BSTree LL_Rotate(BSTree p)
{
    // 左旋 A ↙ B ↙ C  =>  A ↙ B ↘ C
    BSTree rc = p->rchild;
    p->rchild = rc->lchild;
    rc->lchild = p;
    p = rc;
    return p;
}

BSTree LR_Rotate(BSTree p)
{
    p->lchild = LL_Rotate(p->lchild);
    return RR_Rotate(p);
}

BSTree RL_Rotate(BSTree p)
{
    p->rchild = RR_Rotate(p->rchild);
    return LL_Rotate(p);
}

void Insert_Node(BSTree *p,ElemType data){
    BST_node *NewNode = new BST_node();
}